First off, this is a doable project, but a difficult one. Rich text is a tricky beast. If you want a simpler solution using a third party product, our
Midas Rich Text LSX will do this (actually, it was part of a demo I remember showing last year at Lotusphere) with simple calls from LotusScript.
On the other hand, if you have a compelling reason to do this yourself, the basic issue you will have is that you need to read the whole stream of CD records into a new set of buffers, removing the hotspot records which represent the file attachment and replacing them with new records which represent the text message, then remove the original items and replace them with the new items you created.
Added note: Yes, you absolutely can depend on the order of the CD records, but remember that you need to handle each item, so you will use NSFItemInfo and then NSFItemInfoNext until you run out of items. In this case, you are likely to wind up with smaller items, so you can create an item for each item. If you were adding a bunch of information, you would need to worry about not exceeding the MAXONESEGSIZE for an item.